package com.cat.greedyAlgorithm;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-number-of-refueling-stops/description/
 * @create 2025/10/8 19:06
 * @since JDK17
 */

public class Solution58 {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int ans = 0, n = stations.length;
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        for (var station : stations) {
            if (startFuel >= target) {
                return ans;
            }
            while (!heap.isEmpty() && startFuel < station[0] && startFuel < target) {
                startFuel += heap.poll();
                ans++;
            }
            if (startFuel < station[0] && startFuel < target) {  //
                return -1;
            }
            heap.add(station[1]);
        }
        while (!heap.isEmpty() && startFuel < target) {
            startFuel += heap.poll();
            ans++;
        }

        return startFuel >= target ? ans : -1;
    }
}
